/*
 * @lc app=leetcode.cn id=154 lang=cpp
 *
 * [154] 寻找旋转排序数组中的最小值 II
 */

// @lc code=start
class Solution {
public:
    int findMin(vector<int>& nums) {
    /*
        经旋转后数组可能呈现这样
        此时右半侧不满足nums[i] < nums[0]
        为此将数组末尾等于nums[0]的数删除
        删除后进行二分查找即可
          /
         /
       _/    ____
            /
           /
    */
        if(nums.size() == 0) return 0;

        int i = 0, j = nums.size() - 1;
        
        //删除末尾等于nums[0]的数
        while(j >= 0 && nums[j] == nums[i]) j--;

        if(j == -1) return nums[0];

        //如果未进行翻转
        if(nums[j] > nums[i]) return nums[i];
        
        while(i < j){
            int mid = i + j >> 1;
            if(nums[mid] < nums[0]) j = mid;
            else i = mid + 1;
        }

        return nums[i];
    }
};
// @lc code=end

